package com.zklh.leetcode.dynamic;

import java.util.Arrays;

/**
 * 删除并获得点数
 * @author tongnan
 * @date 2025/9/28
 */
public class Solution740 {

    int[] maxDeleteAndEarnForStart;

    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        maxDeleteAndEarnForStart = new int[nums.length];
        return deleteAndEarn(nums, 0);
    }

    public int deleteAndEarn(int[] nums, int start){
        if (start > nums.length - 1) {
            return 0;
        }

        if (start == nums.length - 1) {
            return nums[nums.length-1];
        }

        if (maxDeleteAndEarnForStart[start] != 0) {
            return maxDeleteAndEarnForStart[start];
        }

        int next = start + 1;
        while (next < nums.length && nums[next] == nums[start]) {
            next++;
        }

        int tempScoreForEarnNext = next;
        while (tempScoreForEarnNext < nums.length && nums[tempScoreForEarnNext] == nums[start]+1) {
            tempScoreForEarnNext++;
        }
        int result = Math.max(nums[start]* (next - start) + deleteAndEarn(nums, tempScoreForEarnNext), deleteAndEarn(nums, start + 1));
        maxDeleteAndEarnForStart[start] = result;
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {3, 4, 2};
        int[] nums2 = {2,2,3,3,3,4};
        Solution740 solution740 = new Solution740();
        System.out.println(solution740.deleteAndEarn(nums1));
        System.out.println(solution740.deleteAndEarn(nums2));
    }
}
